1//////////////////////////////////////////////////////////////////////
2// LibFile: triangulation.scad
3// Functions to triangulate polyhedron faces.
4// To use, add the following lines to the beginning of your file:
5// ```
6// use <BOSL/triangulation.scad>
7// ```
8//////////////////////////////////////////////////////////////////////
9
10/*
11BSD 2-Clause License
12
13Copyright (c) 2017, Revar Desmera
14All rights reserved.
15
16Redistribution and use in source and binary forms, with or without
17modification, are permitted provided that the following conditions are met:
18
19* Redistributions of source code must retain the above copyright notice, this
20 list of conditions and the following disclaimer.
21
22* Redistributions in binary form must reproduce the above copyright notice,
23 this list of conditions and the following disclaimer in the documentation
24 and/or other materials provided with the distribution.
25
26THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
27AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
28IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
29DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
30FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
31DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
32SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
33CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
34OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
35OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
36*/
37
38
39use <math.scad>
40
41
42// Section: Functions
43
44
45// Function: face_normal()
46// Description:
47// Given an array of vertices (`points`), and a list of indexes into the
48// vertex array (`face`), returns the normal vector of the face.
49// Arguments:
50// points = Array of vertices for the polyhedron.
51// face = The face, given as a list of indices into the vertex array `points`.
52function face_normal(points, face) =
53 let(count=len(face))
54 normalize(
55 sum(
56 [
57 for(i=[0:count-1]) cross(
58 points[face[(i+1)%count]]-points[face[0]],
59 points[face[(i+2)%count]]-points[face[(i+1)%count]]
60 )
61 ]
62 )
63 )
64;
65
66
67// Function: find_convex_vertex()
68// Description:
69// Returns the index of a convex point on the given face.
70// Arguments:
71// points = Array of vertices for the polyhedron.
72// face = The face, given as a list of indices into the vertex array `points`.
73// facenorm = The normal vector of the face.
74function find_convex_vertex(points, face, facenorm, i=0) =
75 let(count=len(face),
76 p0=points[face[i]],
77 p1=points[face[(i+1)%count]],
78 p2=points[face[(i+2)%count]]
79 )
80 (len(face)>i)?
81 (cross(p1-p0, p2-p1)*facenorm>0)? (i+1)%count : find_convex_vertex(points, face, facenorm, i+1)
82 : //This should never happen since there is at least 1 convex vertex.
83 undef
84;
85
86
87// Function: point_in_ear()
88// Description: Determine if a point is in a clipable convex ear.
89// Arguments:
90// points = Array of vertices for the polyhedron.
91// face = The face, given as a list of indices into the vertex array `points`.
92function point_in_ear(points, face, tests, i=0) =
93 (i<len(face)-1)?
94 let(
95 prev=point_in_ear(points, face, tests, i+1),
96 test=_check_point_in_ear(points[face[i]], tests)
97 )
98 (test>prev[0])? [test, i] : prev
99 :
100 [_check_point_in_ear(points[face[i]], tests), i]
101;
102
103
104// Internal non-exposed function.
105function _check_point_in_ear(point, tests) =
106 let(
107 result=[
108 (point*tests[0][0])-tests[0][1],
109 (point*tests[1][0])-tests[1][1],
110 (point*tests[2][0])-tests[2][1]
111 ]
112 )
113 (result[0]>0 && result[1]>0 && result[2]>0)? result[0] : -1
114;
115
116
117// Function: normalize_vertex_perimeter()
118// Description: Removes the last item in an array if it is the same as the first item.
119// Arguments:
120// v = The array to normalize.
121function normalize_vertex_perimeter(v) =
122 (len(v) < 2)? v :
123 (v[len(v)-1] != v[0])? v :
124 [for (i=[0:len(v)-2]) v[i]]
125;
126
127
128// Function: is_only_noncolinear_vertex()
129// Description:
130// Given a face in a polyhedron, and a vertex in that face, returns true
131// if that vertex is the only non-colinear vertex in the face.
132// Arguments:
133// points = Array of vertices for the polyhedron.
134// facelist = The face, given as a list of indices into the vertex array `points`.
135// vertex = The index into `facelist`, of the vertex to test.
136function is_only_noncolinear_vertex(points, facelist, vertex) =
137 let(
138 face=select(facelist, vertex+1, vertex-1),
139 count=len(face)
140 )
141 0==sum(
142 [
143 for(i=[0:count-1]) norm(
144 cross(
145 points[face[(i+1)%count]]-points[face[0]],
146 points[face[(i+2)%count]]-points[face[(i+1)%count]]
147 )
148 )
149 ]
150 )
151;
152
153
154// Function: triangulate_face()
155// Description:
156// Given a face in a polyhedron, subdivides the face into triangular faces.
157// Returns an array of faces, where each face is a list of three vertex indices.
158// Arguments:
159// points = Array of vertices for the polyhedron.
160// face = The face, given as a list of indices into the vertex array `points`.
161function triangulate_face(points, face) =
162 let(count=len(face))
163 (3==count)?
164 [face]
165 :
166 let(
167 facenorm=face_normal(points, face),
168 cv=find_convex_vertex(points, face, facenorm),
169 pv=(count+cv-1)%count,
170 nv=(cv+1)%count,
171 p0=points[face[pv]],
172 p1=points[face[cv]],
173 p2=points[face[nv]],
174 tests=[
175 [cross(facenorm, p0-p2), cross(facenorm, p0-p2)*p0],
176 [cross(facenorm, p1-p0), cross(facenorm, p1-p0)*p1],
177 [cross(facenorm, p2-p1), cross(facenorm, p2-p1)*p2]
178 ],
179 ear_test=point_in_ear(points, face, tests),
180 clipable_ear=(ear_test[0]<0),
181 diagonal_point=ear_test[1]
182 )
183 (clipable_ear)? // There is no point inside the ear.
184 is_only_noncolinear_vertex(points, face, cv)?
185 // In the point&line degeneracy clip to somewhere in the middle of the line.
186 flatten([
187 triangulate_face(points, select(face, cv, (cv+2)%count)),
188 triangulate_face(points, select(face, (cv+2)%count, cv))
189 ])
190 :
191 // Otherwise the ear is safe to clip.
192 flatten([
193 [select(face, pv, nv)],
194 triangulate_face(points, select(face, nv, pv))
195 ])
196 : // If there is a point inside the ear, make a diagonal and clip along that.
197 flatten([
198 triangulate_face(points, select(face, cv, diagonal_point)),
199 triangulate_face(points, select(face, diagonal_point, cv))
200 ])
201;
202
203
204// Function: triangulate_faces()
205// Description:
206// Subdivides all faces for the given polyhedron that have more than three vertices.
207// Returns an array of faces where each face is a list of three vertex array indices.
208// Arguments:
209// points = Array of vertices for the polyhedron.
210// faces = Array of faces for the polyhedron. Each face is a list of 3 or more indices into the `points` array.
211function triangulate_faces(points, faces) =
212 [
213 for (i=[0 : len(faces)-1])
214 let(facet = normalize_vertex_perimeter(faces[i]))
215 for (face = triangulate_face(points, facet))
216 if (face[0]!=face[1] && face[1]!=face[2] && face[2]!=face[0]) face
217 ]
218;
219
220
221// vim: noexpandtab tabstop=4 shiftwidth=4 softtabstop=4 nowrap